package leetcode.dynamic;

/**
 * @Description: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
 * @Author Ammar
 * @Create 2023/7/15 12:55
 */
public class _121_买卖股票的最佳时机 {
    public int maxProfit(int[] prices) {
        if (prices.length == 1) return 0;
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] <= min) min = prices[i];
            else max = Math.max(prices[i] - min, max);
        }
        return max;
    }

    public int maxProfit1(int[] prices) {
        if (prices.length == 1) return 0;
        int[] gap = new int[prices.length - 1];
        for (int i = 0; i < gap.length; i++) {
            gap[i] = prices[i + 1] - prices[i];
        }
        int dp = gap[0];
        int max = dp;
        for (int i = 1; i < gap.length; i++) {
            dp = Math.max(dp + gap[i], gap[i]);
            max = Math.max(dp, max);
        }
        return Math.max(max, 0);
    }

    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) return 0;
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int[][] dp = new int[s1.length + 1][s2.length + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= s1.length; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= s2.length; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= s1.length; i++) {
            for (int j = 1; j <= s2.length; j++) {
                // 插入一个字符
                int charu = dp[i][j - 1] + 1;
                int shanchu = dp[i - 1][j] + 1;
                int tihuan = dp[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1);
                dp[i][j] = Math.min(Math.min(charu, shanchu), tihuan);
            }
        }
        return dp[s1.length][s2.length];
    }

    public String longestPalindrome(String s) {
        if (s.length() == 1) return s;
        char[] cs = s.toCharArray();
        int begin = 0;
        int maxLen = 1;
        boolean[][] dp = new boolean[cs.length][cs.length];
        // i -> j
        for (int i = cs.length - 1; i >= 0; i--) {
            for (int j = i; j < cs.length; j++) {
                // 从i 到 j 的长度
                int len = j - i + 1;
                if (len <= 2) {
                    dp[i][j] = cs[i] == cs[j];
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
                }
                if (dp[i][j] && len > maxLen) {
                    begin = i;
                    maxLen = len;
                }
            }
        }
        return new String(cs, begin, maxLen);
    }

    public String longestPalindrome1(String s) {
        if (s.length() == 1) return s;
        char[] cs = s.toCharArray();
        int i = 0;
        int maxLen = 1;
        int begin = 0;
        while (i < cs.length) {
            int l = i - 1;
            int r = i;
            while (++r < cs.length && cs[r] == cs[i]);
            i = r;
            while (l >= 0 && r < cs.length && cs[l] == cs[r]) {
                l--;
                r++;
            }
            int len = r - ++l;
            if (len > maxLen) {
                begin = l;
                maxLen = len;
            }
        }
        return new String(cs, begin, maxLen);
    }


}
